PhD

unsupervised.tex (54296B)

---

 \section{Unsupervised Extraction Models}
 \label{sec:relation extraction:unsupervised}
 \begin{epigraph}
 		{Yann LeCun}
 		{Inaugural Lecture at Collège de France}
 		{2016}
 	% This translation comes from a Facebook post made by Yann LeCun himself, but the Collège de France reference should be easier to find.
 	If intelligence was a cake, unsupervised learning would be the cake, supervised learning would be the icing on the cake, and reinforcement learning would be the cherry on the cake.
 \end{epigraph}
 In the unsupervised setting, no samples are labeled with a relation, i.e.~all samples are triplets (sentence, head entity, tail entity) from \(\dataSet\subseteq\sentenceSet\times\entitySet^2\).
 Furthermore, no information about the relation set \(\relationSet\) is available.
 This is problematic since whether a specific semantic link is worthy of appearing in \(\relationSet\) or not is not well defined.
 Having so little information about what constitutes a relation makes the problem intractable if we do not impose some restrictions upon \(\relationSet\).
 All unsupervised models presented in this section are not universal and make some kind of assumption on the structure of the data or on its underlying knowledge base.
 However, developing unsupervised relation extraction models is still interesting for three reasons: they
 \begin{itemize*}
 	\item[(1)] do not necessitate labeled data except for validating the models;
 	\item[(2)] can uncover new relation types; and
 	\item[(3)] can be trained from large unlabeled datasets and then fine-tuned for specific relations.
 \end{itemize*}
 
 For all models, we list the important modeling hypothesis such as \hypothesis{1-adjacency} and \hypothesis{pullback} introduced previously.
 Appendix~\ref{chap:assumptions} contains a list of assumptions with some counterexamples and references to the sections where they were introduced.
 We strongly encourage the reader to refer to it, especially when the implications of a modeling hypothesis is not immediately clear.
 
 \subsection{Evaluation}
 \label{sec:relation extraction:unsupervised evaluation}
 The output of unsupervised models vary widely.
 The main modus operandi can be categorized into two categories:
 \begin{description}
 	\item[Clustering] A first approach is to cluster the samples such that all samples in the same cluster convey the same relation and samples in different clusters convey different relations.
 	\item[Similarity Space] A second approach is to associate each sample with an element of a vector space equipped with a similarity function.
 		If two samples are similar in this vector space, they convey similar relations.
 		This can be seen as a soft version of the clustering approach.
 \end{description}
 
 This distinction has an impact on how we evaluate the models.
 In the first case, standard clustering metrics are used.
 We introduce \bcubed{} \parencite{bcubed}, V-measure \parencite{v-measure} and \textsc{ari} \parencite{ari} in Section~\ref{sec:relation extraction:clustering}.
 They are the most prevalent metrics in cluster evaluation, \bcubed{} in particular is widely used in unsupervised relation extraction.
 In the second case, a few-shot evaluation can be used \parencite{fewrel}.
 We introduce this approach in Section~\ref{sec:relation extraction:few-shot}.
 
 A difficulty of evaluating unlabeled clusters is that we do not know which cluster should be compared to which relation.
 A possible solution to this problem is to use a small number of labeled samples, which can be used to constrain the output of a model to fall into a specific relation set \(\relationSet\).
 This setup is actually similar to semi-supervised approaches such as label propagation (Section~\ref{sec:relation extraction:label propagation}), except that the model must be trained in an unsupervised fashion before being fine-tuned on the supervised dataset.
 Similar to the label propagation model evaluation, unsupervised models evaluated by fine-tuning on a supervised dataset usually report performance varying the number of train labels.
 These performances are measured using the standard supervised metrics introduced in Section~\ref{sec:relation extraction:supervised evaluation}.
 Evaluating performances as a pre-training method can be used for all unsupervised models, in particular similarity-space-based approaches.
 
 \subsubsection{Clustering Metrics}
 \label{sec:relation extraction:clustering}
 In this section, we describe three metrics used to evaluate clustering approaches.
 The first metric, \bcubed{} was first introduced to unsupervised relation extraction by rel-\textsc{lda} (\cite{rellda}, Section~\ref{sec:relation extraction:rellda}), while the other two were proposed as complements by \textcite{fitb} presented in Chapter~\ref{chap:fitb}.
 
 \begin{epigraph}
 		{Valve}
 		{``Portal''}
 		{2007}
 		The cake is a lie.
 \end{epigraph}
 To clearly describe these different clustering metrics, we propose a common probabilistic formulation---in practice, these probabilities are estimated on the validation and test sets---and use the following notations.
 Let \(\rndm{X}\) and \(\rndm{Y}\) be random variables corresponding to samples in the dataset.
 Following Section~\ref{sec:relation extraction:supervised evaluation}, we denote by \(c(\rndm{X})\) the predicted cluster of \(\rndm{X}\) and \(g(\rndm{X})\) its conveyed gold relation.%
 \sidenote{
 	This implies that a labeled dataset is sadly necessary to evaluate an unsupervised clustering model.
 }
 
 \paragraph{B\texorpdfstring{\textsuperscript{3}}{³}}
 The metric most commonly computed for unsupervised model evaluation is a generalization of \fone{} for clustering tasks called \bcubed{} \parencitex{bcubed}.
 The \bcubed{} precision and recall are defined as follows:
 \begin{align*}
 	\bcubed \operatorname{precision}(g, c) & = \expectation_{\rndm{X},\rndm{Y}\sim\uniformDistribution(\dataSet_\relationSet)} P\left(g(\rndm{X})=g(\rndm{Y}) \mid c(\rndm{X})=c(\rndm{Y})\right) \\
 	\bcubed \operatorname{recall}(g, c)    & = \expectation_{\rndm{X},\rndm{Y}\sim\uniformDistribution(\dataSet_\relationSet)} P\left(c(\rndm{X})=c(\rndm{Y}) \mid g(\rndm{X})=g(\rndm{Y})\right) \\
 \end{align*}
 As precision and recall can be trivially maximized by putting each sample in its own cluster or by clustering all samples into a single class, the main metric \bcubed{} \fone{} is defined as the harmonic mean of precision and recall:
 \begin{equation*}
 	\bcubed \fone{}(g, c) = \frac{2}{\bcubed{} \operatorname{precision}(g, c)^{-1} + \bcubed{} \operatorname{recall}(g, c)^{-1}}
 \end{equation*}
 
 While the usual precision (Section~\ref{sec:relation extraction:supervised evaluation}) can be seen as the probability that a sample with a given prediction is correct, the \bcubed{} precision cannot use the correct relation as a reference to determine the correctness of a prediction.
 Instead, whether an assignment is correct is computed as the expectation that a sample is accurately classified relatively to all other samples grouped in the same cluster.
 
 \paragraph{V-measure}
 Another metric is the entropy-based V-measure \parencitex{v-measure}.
 This metric is defined by homogeneity and completeness, which are akin to \bcubed{} precision and recall but rely on conditional entropy.
 For a cluster to be homogeneous, we want most of its elements to convey the same gold relation.
 In other words, the distribution of gold relations inside a cluster must have low entropy.
 This entropy is normalized by the unconditioned entropy of the gold relations to ensure that it does not depend on the size of the dataset:
 \begin{equation*}
 	\operatorname{homogeneity}(g, c) = 1 - \frac{\entropy\left(c(\rndm{X})\mid g(\rndm{X})\right)}{\entropy\left(c(\rndm{X})\right)}.
 \end{equation*}
 Similarly, for a cluster to be complete, we want all the elements conveying the same gold relation to be captured by this cluster.
 In other words, the distribution of clusters inside a gold relation must have low entropy:
 \begin{equation*}
 	\operatorname{completeness}(g, c) = 1 - \frac{\entropy\left(g(\rndm{X})\mid c(\rndm{X})\right)}{\entropy\left(g(\rndm{X})\right)}.
 \end{equation*}
 As  \bcubed{}, the V-measure is summarized by the \fone{} value:
 \begin{equation*}
 	\operatorname{V-measure}(g, c) = \frac{2}{\operatorname{homogeneity}(g, c)^{-1} + \operatorname{completeness}(g, c)^{-1}}.
 \end{equation*}
 \begin{marginfigure}
 	\centering
 	\input{mainmatter/relation extraction/clustering metrics.tex}
 	\scaption[Comparison of \bcubed{} and V-measure.]{
 		Comparison of \bcubed{} and V-measure.
 		Samples conveying three different relations indicated by shape and color are clustered into three boxes.
 		The two rows represent two different clusterings, \bcubed{} favors the first one while V-measure favors the second.
 		V-measure prefers the second clustering since the blue star cluster is kept pure; on the other hand, the green circle cluster is impure no matter what, so its purity is not taken as much into account by the V-measure compared to \bcubed{}.
 		\label{fig:relation extraction:clustering metrics}
 	}
 \end{marginfigure}
 Compared to \bcubed{}, the V-measure penalizes small impurities in a relatively ``pure'' cluster more harshly than in less pure ones.
 Symmetrically, it penalizes a degradation of a well-clustered relation more than of a less-well-clustered one.
 This difference is illustrated in Figure~\ref{fig:relation extraction:clustering metrics}.
 
 \paragraph{Adjusted Rand Index}
 The Rand index (\textsc{ri}, \cite{ri}) is the last clustering metric we consider, it is defined as the probability that cluster and gold assignments are compatible:
 \begin{equation*}
 	\operatorname{\textsc{ri}}(g, c) = \expectation\limits_{\rndm{X},\rndm{Y}} \left[ P\left(
 			    c(\rndm{X})=c(\rndm{Y}) \Leftrightarrow g(\rndm{X})=g(\rndm{Y}) 
 	\right) \right]
 \end{equation*}
 In other words, given two samples, the \textsc{ri} is improved when both samples are in the same cluster and convey the same gold relation or when both samples are in different clusters and convey different relations; otherwise, the \textsc{ri} deteriorates.
 The adjusted Rand index (\textsc{ari}, \citex{ari}) is a normalization of the Rand index such that a random assignment has an \textsc{ari} of 0, and the maximum is 1:
 \begin{equation*}
 	\operatorname{\textsc{ari}}(g, c) =
 		\frac{\displaystyle\operatorname{\textsc{ri}}(g, c) - \expectation_{c\sim\uniformDistribution(\relationSet^\dataSet)}[\operatorname{\textsc{ri}}(g, c)]}
 		{\displaystyle\max_{c\in\relationSet^\dataSet} \operatorname{\textsc{ri}}(g, c) - \expectation_{c\sim\uniformDistribution(\relationSet^\dataSet)}[\operatorname{\textsc{ri}}(g, c)]}
 \end{equation*}
 In practice, the \textsc{ari} can be computed from the elements of the confusion matrix.
 Compared to the previous metrics, \textsc{ari} will be less sensitive to a discrepancy between precision--homogeneity and recall--completeness since it is not a harmonic mean of both.
 
 \subsubsection{Few-shot}
 \label{sec:relation extraction:few-shot}
 \begin{marginparagraph}
 	This section only presents Few-shot evaluation.
 	It is possible---and quite common---to train a model using a few-shot objective, usually as a fine-tuning phase before a few-shot evaluation.
 	Since we are mostly interested in unsupervised approaches, we do not delve into few-shot training.
 	See \textcite{fewrel} for details.
 \end{marginparagraph}
 Clustering metrics are problematic since producing a clustering with no a priori knowledge on the relation schema \(\relationSet\) leads to unsolvable problems:
 \begin{itemize}
 	\item Should the relation \textsl{sibling} be cut into \textsl{brother} and \textsl{sister}?
 	\item Is the relation between a country and its capital the same as the one between a county and its seat?
 	\item Is the ear \textsl{part of} the head in the same fashion that the star Altair is \textsl{part of} the Aquila constellation?
 \end{itemize}
 All of these questions can be answered differently depending on the design of the underlying knowledge base.
 However, unsupervised clustering algorithms do not depend on \(\relationSet\).
 They must decide whether ``Phaedra is the sister of Ariadne'' and ``Castor is the brother of Pollux'' go inside the same cluster independently of these design choices.
 
 Fine-tuning on a supervised dataset solves this problem but adds another.
 The evaluation no longer assesses the proficiency of a model to learn from unlabeled data alone; it also evaluates its ability to adapt to labeled samples.
 Furthermore, the smaller the labeled dataset is, the more results have high variance.
 On the other hand, the larger the labeled dataset is, the less the experiment evaluates the unsupervised phase.
 
 A few-shot evaluation can be used to answer these caveats.
 Instead of evaluating a clustering of the samples, few-shot experiments evaluate a similarity function between samples: \(\operatorname{sim}\colon \dataSet\times\dataSet\to\symbb{R}\).
 Given a query sample \(x^{(q)}\) and a set of candidates \(\vctr{x}^{(c)}=\{x_i^{(c)}\mid i=1,\dotsc,C\}\), %
 \begin{marginparagraph}
 	\(C\) is the number of candidates, in Table~\ref{tab:relation extraction:few-shot problem} we have \(C=5\).
 \end{marginparagraph}
 the model is evaluated on whether it is able to find the candidate conveying the same relation as the query.
 This is simply reported as an accuracy by comparing \(\argmax_{x\in\vctr{x}^{(c)}} \operatorname{sim}(x^{(q)}, x)\) with the correct candidate.
 
 \begin{table}[ht!]
 	\centering
 	\input{mainmatter/relation extraction/few-shot problem.tex}
 	\sidecaption[Few-shot problem.]{
 		Few-shot problem.
 		For ease of reading, the entity identifiers---such as \wdent{450036} for ``Hörsel''---are not given.
 		Both the query and the third candidate convey the relation \wdrel{206} \textsl{located in or next to body of water}.
 		\label{tab:relation extraction:few-shot problem}
 	}
 \end{table}
 
 Table~\ref{tab:relation extraction:few-shot problem} gives an example of a few-shot problem.
 It illustrates the five-way one-shot problem, meaning that we must choose a relation among five and that each of the five relations is represented by a single sample.
 Another popular variant is the ten-way five-shot problem: the candidates are split into ten bags of five samples each, all samples in a bag convey the same relation, and the goal is to predict the bag in which the query belongs.
 \begin{marginparagraph}
 	Quite confusingly, they can also be referred to as ``meta-train'' and ``meta-test.''
 	Indeed, to follow the usual semantic of the ``meta-'' prefix, the ``meta-sets'' should refer to sets of \((\text{query}, \text{candidates})\) tuples, not the candidates themselves.
 \end{marginparagraph}
 Candidates are sometimes referred to as ``train set'' and the query as ``test set'' since this can be seen as an extremely small dataset with five training samples and one test sample.
 
 FewRel, described in Section~\ref{sec:datasets:fewrel}, is the standard few-shot dataset.
 In FewRel, Altair is not \wdrel{361} \textsl{part of} Aquila, it is \wdrel{59} \textsl{part of constellation} Aquila.
 However, this design decision does not influence the evaluation.
 Given the query ``Altair is located in the Aquila constellation,'' a model ought to rank this sample as more similar to samples conveying \textsl{part of constellation} than to those conveying other kinds of \textsl{part of} relationships.
 If FewRel made the opposite design choice, the model would still be able to achieve high accuracy by ensuring \textsl{part of} samples are similar.
 The decision to split or not the \textsl{part of} relation should be of no concern to the unsupervised model.
 
 \subsection{Open Information Extraction}
 \label{sec:relation extraction:oie}
 In Open information extraction (\textsc{oie}, \citex{oie}), the closed-domain assumption (Section~\ref{sec:relation extraction:domain restriction}) is neither made for relations nor entities, which are extracted jointly.
 Instead \(\entitySet\) and \(\relationSet\) are implicitly defined from the language itself, typically a fact \((e_1, r, e_2)\) is expressed as a triplet such as (noun phrase, verb phrase, noun phrase).
 This makes \textsc{oie} particularly interesting when processing large amounts of data from the web, where there can be many unanticipated relations of interest.
 
 This section focuses on TextRunner, the first model implementing \textsc{oie}.
 It uses an aggregate extraction setup where \(\dataSet\) is directly mapped to \(\kbSet\), with the peculiarity that \(\kbSet\) is defined using surface forms only.
 The hypothesis on which TextRunner relies is that the surface form of the relation conveyed by a sentence appears in the path between the two entities in its dependency tree.
 In the \textsc{oie} setup, these surface forms can then be used as labels for the conveyed relations, thereby using the language itself as the relation domain \(\relationSet\).
 TextRunner can be split into three parts:
 \begin{description}
 	\item[The Learner] is a naive Bayes classifier, trained on a small dataset to predict whether a fact \((e_1, r, e_2)\) is trustworthy.
 		To extract a set of samples for this task, a dependency parser (Figure~\ref{fig:relation extraction:dependency tree}) is run on the dataset and tuples \((e_1, r, e_2)\) are extracted where \(e_1\) and \(e_2\) are base noun phrases and \(r\) is the dependency path between the two entities.
 		The tuples are then automatically labeled as trustworthy or not according to a set of heuristics such as the length of the dependency path and whether it crosses a sentence boundary.
 		The naive Bayes classifier is then trained to predict the trustworthiness of a tuple given a set of hand-engineered features (Section~\ref{sec:relation extraction:hand-designed features}).
 	\item[The Extractor] extracts trustworthy facts on the whole dataset.
 		The features on which the Learner is built only depend on part-of-speech (\textsc{pos}) tags (noun, verb, adjective\dots) such that the Extractor does not need to run a dependency parser on all the sentences in the entire dataset.
 		\begin{marginparagraph}
 			Dependency parsers tend to be a lot slower than \textsc{pos} taggers.
 		\end{marginparagraph}
 		While the Learner uses the dependency path for \(r\), the Extractor uses the infix from which non-essential phrases (such as adverbs) are eliminated heuristically.
 		Thus the Extractor simply runs a \textsc{pos} tagger on all sentences, finds all possible entities \(e\), estimates a probable relation \(r\) and filters them using the Learner to output a set of trustworthy facts.
 	\item[The Assessor] assigns a probability that a fact is true from redundancy in the dataset using the urns model of \textcite{textrunner_assessor}.
 		This model uses a binomial distribution to model the probability that a correct fact appears \(k\) times among \(n\) extractions with a fixed repetition rate.
 		Furthermore, it assumes both correct and incorrect facts follow different Zipf's laws.
 		The shape parameter \(s_I\) of the distribution of incorrect facts is assumed to be 1.
 		While the shape parameter \(s_C\) of the distribution of correct facts as well as the number of correct facts \(N_C\) are estimated using an expectation--maximization algorithm.
 		\begin{marginparagraph}[-3mm]
 			Zipf's law comes from the externalist linguistic school.
 			It follows from the observation that the frequency of the second most common word is half the one of the most frequent word, that the one of the third most common word is a third of the one of the most frequent, etc.
 			The same distribution can often be observed in information extraction.
 			Zipf's law is parametrized by a shape \(s\) and the number of elements \(N\):
 			\begin{equation*}
 				P(x\mid s) \propto
 					\begin{cases}
 						x^{-s} & \text{ for } x\in\{1,\dotsc,N\} \\
 						0 & \text{ otherwise } \\
 					\end{cases}
 			\end{equation*}
 			A Zipf's law is easily recognizable on a \(\log\)--\(\log\) scale, its probability mass function being a straight line.
 			Take for example the Zipf's law with parameters \(s=2\) and \(N=10\):
 			\begin{center}
 				\input{mainmatter/relation extraction/zipf.tex}
 			\end{center}
 		\end{marginparagraph}
 		In the expectation step, the binomial and Zipf distribution assumptions can be combined using Bayes' theorem to estimate whether a fact is correct or not.
 		In the maximization step, the parameters \(s_C\) and \(N_C\) are estimated.
 \end{description}
 
 \textcite{oie} compare their approach to KnowItAll, an earlier work similar to \textsc{oie} but needing a list of relations (surface forms) as input to define the target relation schema \(\relationSet\).
 On a set of ten relations, they manually labeled the extracted facts as correct or not, obtaining an error rate of 12\% for TextRunner and 18\% for KnowItAll.
 They further run their model on 9 million web pages, extracting 7.8 million facts.
 
 A limitation of the \textsc{oie} approach is that it heavily depends on the raw surface form and suffers from bad generalization.
 The two facts ``Bletchley Park \textsl{known as} Station X'' and ``Bletchley Park \textsl{codenamed} Station X'' are considered different by TextRunner since the surface forms conveying the relations in the underlying sentences are different.
 Subsequent \textsc{oie} approaches try to address this problem, such as \textcite{textrunner_synonym}, which extend TextRunner with a resolver \parencite{textrunner_resolver} to merge synonyms.
 However, this problem is not overcome yet and is still an active area of research.
 Furthermore, since the input of \textsc{oie} systems is often taken to be the largest possible chunk of the web, and since the extracted facts do not follow a strict nomenclature, a fair evaluation of \textsc{oie} systems among themselves or to other unsupervised relation extraction models is still not feasible.
 
 \subsection{Clustering Surface Forms}
 \label{sec:relation extraction:hasegawa}
 The first unsupervised relation extraction model was the clustering approach of \textcitex{hasegawa}.
 It is somewhat similar to \textsc{dirt} (Section~\ref{sec:relation extraction:dirt}) in that it uses a similarity between samples.
 However, their work goes one step further by using this similarity to build relation classes.
 Furthermore, \textcite{hasegawa} does not assume \hypothesis{pullback}, i.e.~it does not assume that the sentence and entities convey the relation separately, on their own.
 Instead, its basic assumption is that the infix between two entities is the expression of the conveyed relation.
 \begin{marginparagraph}
 	As a reminder, the infix is the span of text between the two entities in the sentence.
 \end{marginparagraph}
 As such, if two infixes are similar, the sentences convey similar relations.
 Furthermore, \textsc{ner} (see the introduction of Chapter~\ref{chap:relation extraction}) is performed on the text instead of simple entity chunking.
 This means that all entities are tagged with a type such as ``organization'' and ``person.''
 These types strongly constrain the relations through the following assumption:
 \begin{marginparagraph}[-9mm]
 	Following Section~\ref{sec:context:relation algebra}, \(\breve{r}\) is the converse relation of \(r\), i.e.~the relation with \(e_1\) and \(e_2\) in the reverse order.
 	\(\relationComposition\) is the composition operator and \(\relationOne_X\) the complete relation over \(X\).
 	\(r\relationComposition\breve{r}\) is the relation linking all the entities which appear as subject (\(e_1\), on the left hand side) of \(r\) to themselves.
 	This relation is constrained to be between entities in \(X\).
 	Less relevant to this formula, \(r\relationComposition\breve{r}\) also links together entities linked by \(r\) to the same object.
 \end{marginparagraph}
 \begin{assumption}{type}
 	All entities have a unique type, and all relations are left and right restricted to one of these types.
 
 	\smallskip
 	\noindent
 	\(
 		\exists \symcal{T} \textup{ partition of } \entitySet :
 		\forall r\in\relationSet :
 		\exists X, Y\in \symcal{T} :
 		r\relationComposition \breve{r} \relationOr \relationOne_X = \relationOne_X
 		\; \land \;
 		\breve{r}\relationComposition r \relationOr \relationOne_Y = \relationOne_Y
 	\)
 \end{assumption}
 \begin{marginparagraph}[9mm]
 	Here, we assume that the partition \(\symcal{T}\) is not degenerate and somewhat looks like a standard \textsc{ner} classification output.
 	Otherwise, \(\symcal{T}=\{\entitySet\}\) is a valid partition of \(\entitySet\), and this assumption is tautological.
 \end{marginparagraph}
 This is a natural assumption for many relations; for example, the relation \textsl{born in} is always between a person and a geopolitical entity (\textsc{gpe}).
 
 Given a pair of entities \((e_1, e_2)\in\entitySet^2\), \textcite{hasegawa} collect all samples in which they appear and extract a single vector representation from all these samples.
 This representation is built from the bag of words of the infixes weighted by \textsc{tf--idf} (term frequency--inverse document frequency).
 Since a bag of words discards the ordering of the words or entities, the variant of \textsc{tf--idf} used takes into account the directionality:
 \begin{align*}
 	\textsc{tf}(w, e_1, e_2) = &
 			 \text{number of times \(w\) appears between \(e_1\) and \(e_2\)} \\
 			& \hspace{5mm} - \text{number of times \(w\) appears between \(e_2\) and \(e_1\)} \\
 	\textsc{idf}(w) = & (\text{number of documents in which \(w\) appears})^{-1}
 	\\
 	\textsc{tf--idf}(w, e_1, e_2) = & \textsc{tf}(w, e_1, e_2) \cdot \textsc{idf}(w)
 \end{align*}
 
 From this definition we obtain a representation \(\vctr{z}_{e_1, e_2}\in\symbb{R}^{V}\) of the pair \((e_1, e_2)\in\entitySet^2\) by taking the value of \(\textsc{tf--idf}(w, e_1, e_2)\) for all \(w\in V\).
 Given two entity pairs, their similarity is defined as follow:
 \begin{equation*}
 	\operatorname{sim}(\vctr{e}, \vctr{e}')
 	= \cos(\vctr{z}_\vctr{e}, \vctr{z}_\vctr{e'})
 	= \frac{\vctr{z}_\vctr{e} \cdot \vctr{z}_\vctr{e'}}{\|\vctr{z}_\vctr{e}\| \|\vctr{z}_\vctr{e'}\|}.
 \end{equation*}
 
 Using this similarity function, the complete-linkage clustering algorithm%
 \sidenote{
 	The complete-linkage algorithm is an agglomerative hierarchical clustering method also called farthest neighbor clustering.
 	The algorithm starts with each sample in its own cluster then merges the clusters two by two until reaching the desired number of clusters.
 	At each step, the two closest clusters are merged together, with the distance between clusters being defined as the distance between their farthest elements.
 }
 \parencite{complete_linkage} is used to extract relations classes.
 Since each pair end up in a single cluster, this assumes \hypothesis{1-adjacency}.
 \Textcite{hasegawa} evaluate their method on articles from the New York Times (\textsc{nyt}).
 They extract relations classes by first clustering all \(\vctr{z}_{e_1, e_2}\) where \(e_1\) has the type person and \(e_2\) has the type \textsc{gpe}, and then by clustering all \(\vctr{z}_{e_1, e_2}\) where both \(e_1\) and \(e_2\) are organizations.
 By clustering separately different type combinations, they ensure that \hypothesis{type} is enforced.
 
 They furthermore experiment with automatic labeling of the clusters with the most frequent word appearing in the samples.
 Apart from the relation \textsl{prime minister}, which is simply labeled ``minister'' since only unigrams are considered, the labels are rather on point.
 To measure the performance of their model, they use a classical supervised \fone{} where each cluster is labeled by the majority gold relation.
 Using this somewhat unadapted metric, they reach an \fone{} of 82\% on person--\textsc{gpe} pairs and an \fone{} of 77\% on organization--organization pairs.
 This relatively high score compared to subsequent models can be explained by the small size of their dataset, which is further split by entity type.
 Furthermore, note that some generic relations such as \textsl{part of} do not follow \hypothesis{type} and, as such, cannot be captured.
 
 \subsection{Rel-\textsc{lda}}
 \label{sec:relation extraction:rellda}
 Rel-\textsc{lda} \parencitex{rellda} is a probabilistic generative model inspired by \textsc{lda}.
 It works by clustering sentences: each relation defines a distribution over a handcrafted set of sentence features (Section~\ref{sec:relation extraction:hand-designed features}) describing the relationship between the two entities in the text.
 Furthermore, rel-\textsc{lda} models the propensity of a relation at the level of the document; thus, it is not strictly speaking a sentence-level relation extractor.
 The idea behind modeling this additional information is that when a relation such as \wdrel{413} \textsl{position played on team} appears in a document, other relations pertaining to sports are more likely to appear.
 Figure~\ref{fig:relation extraction:rellda plate} gives the plate diagram for the rel-\textsc{lda} model.
 It uses the following variables:
 \begin{itemize}[nosep,label={}]
 	\item \(\rndmvctr{f}_i\) the features of the \(i\)-th sample, where \(\rndm{f}_{ij}\) is its \(j\)-th feature
 	\item \(\rndm{r}_i\) the relation of the \(i\)-th sample
 	\item \(\rndm{\theta}_d\) the distribution of relations in the document \(d\)
 	\item \(\rndm{\phi}_{rj}\) the probability of the \(j\)-th feature to occurs for the relation \(r\)
 	\item \(\alpha\) the Dirichlet prior for \(\rndm{\theta}_d\)
 	\item \(\beta\) the Dirichlet prior for \(\rndm{\phi}_{rj}\)
 \end{itemize}
 The generative process is listed as Algorithm~\ref{alg:relation extraction:rellda generation}.
 The learning process uses the expectation--maximization algorithm.
 In the variational E-step, the relation for each sample \(r_i\) is sampled from the categorical distribution:
 \begin{equation*}
 	P(r_i\mid \vctr{f}_i, d) \propto P(r_i\mid d) \prod_{j=1}^m P(f_{ij}\mid r_i)
 \end{equation*}
 \begin{marginfigure}
 	\centering
 	\input{mainmatter/relation extraction/rellda plate.tex}
 	\scaption[Rel-\textsc{lda} plate diagram.]{
 		Rel-\textsc{lda} plate diagram.
 		\(D\) is the number of documents in the dataset and \(n_d\) is the number of samples in the document \(d\).
 		For each sample \(i\), there are several features \(\rndm{f}_{i1}, \rndm{f}_{i2}, \dotsc, \rndm{f}_{im}\), accordingly for each relation \(r\), there are also several feature priors \(\rndm{\phi}_{r1}, \dotsc, \rndm{\phi}_{rm}\), however for simplicity, a single prior is shown here.
 		\label{fig:relation extraction:rellda plate}
 	}
 \end{marginfigure}%
 \begin{marginalgorithm}
 	\centering
 	\input{mainmatter/relation extraction/rellda.tex}
 	\scaption[The rel-\textsc{lda} generative process.]{
 		The rel-\textsc{lda} generative process.
 		\(\operatorname{Dir}\) are Dirichlet distributions.
 		\(\operatorname{Cat}\) are categorical distributions.
 		\label{alg:relation extraction:rellda generation}
 	}
 \end{marginalgorithm}%
 where \(P(r\mid d)\) is defined by \(\theta_d\) and \(P(f_{ij}\mid r)\) is defined by \(\phi_{rj}\).
 In the M-step, the values for \(\theta_d\) are computed by counting the number of times each relation appears in \(d\) and the hyperprior \(\alpha\); and the value for \(\phi_{rj}\) is computed from the number of co-occurrences of the \(j\)-th feature with the relation \(r\) and from \(\beta\).
 
 \Textcite{rellda} evaluate their model on the New York Times by comparing their clusters to relations in Freebase.
 However, because of the incompleteness of knowledge bases, they only evaluate the recall on Freebase and use manual annotation to estimate the precision.
 Even though the original article lacks a significant comparison, subsequent approaches often compare to rel-\textsc{lda}.
 
 A first limitation of their approach is that given the relation \(r\), the features \(f\) are independents.
 Since the entities are among those features, this means that \(P(e_2\mid e_1, r) = P(e_2\mid r)\) which is clearly false.
 \begin{assumption}{biclique}
 	Given a relation, the entities are independent of one another: \( \displaystyle \rndm{e}_1 \independent \rndm{e}_2 \mid \rndm{r} \).
 	In other words, given a relation, all possible head entities are connected to all possible tail entities.
 	
 	\smallskip
 	\noindent
 	\(\forall r\in\relationSet:\exists A,B\subseteq\entitySet: r\relationComposition\breve{r}=\relationOne_A\land\breve{r}\relationComposition r=\relationOne_B\)
 \end{assumption}
 This is a widespread problem with generative models which are inclined to make extensive independence assumptions.
 Furthermore, generative models have an implicit bias that all observed features are related to relation extraction, even though they might measures other aspect of the sample (style, idiolectal word choice, etc).
 This might results in the model focusing on features not related to the relation extraction task.
 
 Several extensions of rel-\textsc{lda} were proposed.
 Type-\textsc{lda} \parencite{rellda} purpose to model entity types which are latent variables of entity features, themselves generated from the relation variable \(r\), thus softly enforcing \hypothesis{type}.
 Sense-\textsc{lda} \parencitex{rellda_sense} use a \textsc{lda}-like model for each different dependency path.
 Clusters for different paths are then merged into relation clusters.
 
 Rel-\textsc{lda} is an important work in that it proposes a simple evaluation framework; in particular, it introduces the \bcubed{} metric to unsupervised relation extraction.
 However, it predates the advent of neural networks and distributed representations in relation extraction, by which it was bound to be replaced.
 
 \subsection{Variational Autoencoder for Relation Extraction}
 \label{sec:relation extraction:vae}
 \Textcitex{vae_re} were first to propose a discriminative unsupervised relation extraction model.
 Discriminative models directly solve the inference problem of finding the posterior \(P(r\mid x)\).
 This is in contrast to generative models such as rel-\textsc{lda} which determine \(P(x\mid r)\) and then use Bayes' theorem to compute \(P(r\mid x)\) and make a prediction.
 The model of \textcite{vae_re} is closely related to the approach presented in Chapter~\ref{chap:fitb}.
 It is a clustering model, meaning that it produces clusters of samples where the samples in each cluster all convey the same relation.
 To do so, it uses a variational autoencoder model (\textsc{vae}, \citex{vae}) that we now describe.
 
 \paragraph{Variational Autoencoder}
 \begin{marginfigure}
 	\centering
 	\input{mainmatter/relation extraction/vae plate.tex}
 	\scaption[\textsc{vae} plate diagram.]{
 		\textsc{vae} plate diagram.
 		\(N\) is the number of samples in the dataset.
 		\label{fig:relation extraction:vae plate}
 	}
 \end{marginfigure}
 The goal of a variational autoencoder is to learn a latent variable \(\vctr{z}\) which explains the distribution of an observed variable \(\vctr{x}\).
 For our problem, the latent variable corresponds to the relation conveyed by the sample \(\vctr{x}\).
 We assume we know the generative process \(P(\vctr{x}\mid \vctr{z}; \vctr{\theta})\), i.e.~this process is the ``decoder'' (parametrized by \(\vctr{\theta}\)): given the latent variable it produces a sample.
 However, the process of interest to us is to estimate the latent variable---the relation---from a sample, that is \(P(\vctr{z}\mid\vctr{x}; \vctr{\theta})\).
 Using Bayes' theorem we can reformulate this posterior as \(P(\vctr{x}\mid \vctr{z}; \vctr{\theta})P(\vctr{z}\mid \vctr{\theta}) \divslash P(\vctr{x}\mid \vctr{\theta})\).
 However, computing \(P(\vctr{x}\mid \vctr{\theta})\) is often intractable, especially when the likelihood \(P(\vctr{x}\mid \vctr{z}; \vctr{\theta})\) is modeled using a complicated function like a neural network.
 To solve this problem, a variational approach is used: another model \(Q\) parametrized by \(\vctr{\phi}\) is used to approximate \(P(\vctr{z}\mid\vctr{x}; \vctr{\theta})\) as well as possible.
 This approximation \(Q(\vctr{z}\mid\vctr{x};\vctr{\phi})\) is the ``encoder'' since it finds the latent variable associated with a sample.
 The model can then be trained by maximizing the log-likelihood given the latent variable estimated by \(Q\) and by minimizing the difference between the latent variable predicted by \(Q\) and the desired prior \(P(\vctr{z}\mid\vctr{\theta})\):
 \begin{equation}
 	J_\textsc{elbo}(\vctr{\theta}, \vctr{\phi}) = \expectation_{Q(\vctr{z}\mid \vctr{x}; \vctr{\phi})}[\log P(\vctr{x}\mid\vctr{z};\vctr{\theta})] - \kl(Q(\vctr{z}\mid \vctr{x}; \vctr{\phi}) \mathrel{\|} P(\vctr{z}\mid\vctr{\theta}))
 	\label{eq:relation extraction:elbo}
 \end{equation}
 A justification for this objective can also be found in the fact that it's a lower bound of the log marginal likelihood \(\log P(\vctr{x}\mid \vctr{\theta})\), hence its name: evidence lower bound (\textsc{elbo}).
 The first part of the objective is often referred to as the negative reconstruction loss since it seeks to reconstruct the sample \(\vctr{x}\) after it went through the encoder \(Q\) and the decoder \(P\).
 One last problem with the \textsc{vae} approximation relates to the reconstruction loss, the estimation of the expectation over \(Q(\vctr{z}\mid\vctr{x};\vctr{\phi})\) not being differentiable which makes the model---in particular \(\vctr{\phi}\)---untrainable by gradient descent.
 This is usually solved using the reparameterization trick: sampling from \(Q(\vctr{z}\mid\vctr{x};\vctr{\phi})\) can often be done in a two steps process: sampling from a simple distribution like \(\epsilon\sim\normalDistribution(0, 1)\) then transforming this sample using a deterministic process parametrized by \(\vctr{\phi}\).
 The plate diagram of the \textsc{vae} is given Figure~\ref{fig:relation extraction:vae plate} where the model \(P\) is marked with solid lines and the variational approximation \(Q\) is marked with dashed lines.
 
 \begin{marginfigure}
 	\centering
 	\input{mainmatter/relation extraction/marcheggiani plate.tex}
 	\scaption[\textcite{vae_re} plate diagram.]{
 		\textcite{vae_re} plate diagram.
 		\label{fig:relation extraction:marcheggiani plate}
 	}
 \end{marginfigure}
 
 \bigskip
 
 Coming back to the model of \textcite{vae_re}, it is a conditional \(\beta\)\textsc{-vae},%
 \sidenote{
 	The \(\beta\) in ``\(\beta\)\textsc{-vae}'' simply indicates that the Kullback--Leibler term in Equation~\ref{eq:relation extraction:elbo} is weighted by a hyperparameter \(\beta\).
 	More details are given in Chapter~\ref{chap:fitb}.
 }
 i.e.~the whole process is conditioned on an additional variable.
 Indeed, in their approach, only the entities \(\vctr{e}\in\entitySet^2\) are reconstructed, while the sentence \(s\in\sentenceSet\) simply conditions the whole process.
 The latent variable explaining the observed entities is expected to be the relation conveyed by the sample.
 The resulting model's plate diagram is given in Figure~\ref{fig:relation extraction:marcheggiani plate}.
 This approach is defined by two models:
 \begin{description}
 	\item[The Encoder] \(Q(\rndm{r}\mid\vctr{e}, s; \vctr{\phi})\) is the relation extraction model properly speaking.
 		It is defined as a linear model on top of handcrafted features (Section~\ref{sec:relation extraction:hand-designed features}).
 		For each sample, the model outputs a distribution over a predefined number of relations.
 	\item[The Decoder] \(P(\vctr{e}\mid r; \vctr{\theta})\) is a model estimating how likely it is for two entities to be linked by a relation.
 		It is a reconstruction model since the entities \(\vctr{e}\) are known and need to be retrieved from the latent relation \(r\) sampled from the encoder.
 		It is defined using selectional preferences (Section~\ref{sec:context:selectional preferences}) and \textsc{rescal} (Section~\ref{sec:context:rescal}).
 \end{description}
 Note that to label a sample \((\vctr{e}, s)\in\dataSet\), \textcite{vae_re} simply select \(\argmax_{r\in\relationSet} Q(r\mid \vctr{e}, s; \vctr{\phi})\), meaning that the decoder is not used during evaluation.
 Its sole purpose is to provide a supervision signal to the encoder through the maximization of \(J_\textsc{elbo}\).
 The whole autoencoder can also be interpreted as being trained by a surrogate task of filling-in entity blanks.
 This is the interpretation we use in Chapter~\ref{chap:fitb}.
 
 For Equation~\ref{eq:relation extraction:elbo} to be well defined, a prior on the relations must also be selected; \textcite{vae_re} make the following assumption:
 \begin{assumption}{uniform}
 	All relations occur with equal frequency.
 	
 	\smallskip
 	\noindent
 	\( \displaystyle \forall r\in\relationSet\colon P(r) = \frac{1}{|\relationSet|} \)
 \end{assumption}
 
 They evaluate their approach on the New York Times distantly supervised by Freebase.
 By inducing 100 clusters, they show an improvement of the \bcubed{} \fone{} compared to \textsc{dirt} (Section~\ref{sec:relation extraction:dirt}) and rel-\textsc{lda} (Section~\ref{sec:relation extraction:rellda}).
 They also experiment using semi-supervised evaluation (Section~\ref{sec:relation extraction:unsupervised evaluation}) by pre-training their decoder on a subset of Freebase before training their encoder as described above; this additional supervision improves the \fone{} by more than 27\%.
 These results were further improved by \textcite{vae_re2}, which proposed to split the latent variable into a relation \(r\) and sentence information \(z\), with \(z\) conditioned on \(r\) and using a loss including the reconstruction of the sentence \(s\) from \(z\).
 
 \subsection{Matching the Blanks}
 \label{sec:relation extraction:mtb}
 Matching the blanks (\textsc{mtb}, \citex{mtb}) is an unsupervised method that does not attempt to cluster samples but rather learns a representation of the relational semantics they convey.
 More precisely, this representation is used to measure the similarity between samples such that similar samples convey similar relations.
 As such, it is either evaluated as a supervised pre-training method (Section~\ref{sec:relation extraction:unsupervised evaluation}) or using a few-shot dataset (Section~\ref{sec:relation extraction:few-shot}).
 The \textsc{mtb} article introduces several methods to extract an entity-aware representation of a sentence using \textsc{bert}; this was discussed in Section~\ref{sec:relation extraction:mtb sentential}.
 This section focuses on the unsupervised training.
 As a reminder, we refer to sentence encoder of \textsc{mtb} by the function \(\bertcoder\colon\sentenceSet\to\symbb{R}^d\) illustrated Figure~\ref{fig:relation extraction:emes}.
 Given this encoder, \textsc{mtb} defines the similarity between samples as:
 \begin{equation}
 	\operatorname{sim}(s, s') = \sigmoid(\bertcoder(s)\transpose\bertcoder(s'))
 	\label{eq:relation extraction:mtb similarity}
 \end{equation}
 This similarity function can be used to evaluate the model on a few-shot task.
 Note that this function completely ignores entities identifiers (e.g.\ \wdent{211539}), but can still exploit the entities surface forms (e.g.\ ``Peter Singer'') through the sentence \(s\in\sentenceSet\).
 This model can be used as is, without any training other than the masked language model pre-training of \textsc{bert} (Section~\ref{sec:context:mlm}) and reach an accuracy of 72.9\% on the FewRel 5 way 1 shot dataset.
 
 \Textcite{mtb} propose a training objective to fine-tune \textsc{bert} for the unsupervised relation extraction task.
 This objective is called matching the blanks.
 It assumes that two sentences containing the same entities convey the same relation.
 This is exactly \hypothesis{1-adjacency} as given Section~\refAssumptionSection{oneadjacency}.
 The probability that two sentences convey the same relation (\(\rndm{D}=1\)) is taken from the similarity function: \(P(\rndm{D}=1\mid s, s')=\operatorname{sim}(s, s')\).
 Given this, the \hypothesis{1-adjacency} assumption is translated into the following negative sampling (Section~\ref{sec:context:negative sampling}) loss:
 \begin{equation}
 	\loss{mtb} = \frac{-1}{|\dataSet|^2} \sum_{\substack{(\vctr{e}, s)\in\dataSet\\(\vctr{e}', s')\in\dataSet}}
 	\begin{array}[t]{l}
 		\delta_{\vctr{e},\vctr{e}'} \log P(\rndm{D}=1\mid s, s') \\
 		\hspace{1cm} + (1 - \delta_{\vctr{e},\vctr{e}'}) \log P(\rndm{D}=0\mid s, s') \\
 	\end{array}
 	\label{eq:relation extraction:mtb loss}
 \end{equation}
 This loss is minimized through gradient descent by sampling random positive and negative sentence pairs.
 These pairs can be obtained by comparing the entity identifier without the need for any supervision.
 
 A problem with this approach is that the \bertcoder{} model can simply learn to perform entity linking on the entities surface forms in the sentences \(s\), thus minimizing Equation~\ref{eq:relation extraction:mtb loss} by predicting whether \(\vctr{e}=\vctr{e}'\).
 We want to avoid this since this would only work on samples seen during training and would not generalize to unseen entities.
 To ensure the model predicts whether the samples convey the same relation from the sentences \(s\) and \(s'\) alone, blanks are introduced.
 A special token \blanktag{} is substituted to the entities as follow:
 \begin{indentedexample}
 	\uhead{\blanktag}, inspired by Cale's earlier cover, recorded one of the most acclaimed versions of ``\utail{\blanktag}.''\\
 	\smallskip
 	\uhead{\blanktag}'s rendition of ``\utail{\blanktag}'' has been called ``one of the great songs'' by Time\dots
 \end{indentedexample}
 This is similar to the sample corruption of \textsc{bert} (Section~\ref{sec:context:mlm}), indeed like \textsc{bert}, the entity surface forms are blanked only a fraction%
 \sidenote{\Textcite{mtb} blanks each entity with a probability of 70\%, meaning that only 9\% of training samples have both of their entity surface forms intact.}
 of the time so as to not confuse the model when real entities appear during evaluation.
 
 Another problem with Equation~\ref{eq:relation extraction:mtb loss} is that the negative sample space \(\vctr{e}\neq\vctr{e}'\) is extremely large.
 Instead of taking negative samples randomly in this space, \textcite{mtb} propose to take only samples which are likely to be close to positive ones.
 To this end, the \(\vctr{e}\neq\vctr{e}'\) condition is actually replaced with the following one:
 \begin{equation*}
 	|\{e_1, e_2\} \cap \{e_1', e_2'\}| = 1
 \end{equation*}
 These are called ``strong negatives'': negative samples that have precisely one entity in common.
 Negative sampling, especially with strong negatives, leads to another unfortunate assumption:
 \begin{assumption}[onetoone]{\(1\to1\)}
 	All relations are one-to-one.
 
 	\smallskip
 	\noindent
 	\( \forall r\in\relationSet\colon
 	r\relationComposition \breve{r} \relationOr \relationIdentity
 	= \breve{r}\relationComposition r \relationOr \relationIdentity
 	= \relationIdentity \)
 \end{assumption}
 Indeed, if a relation is not one-to-one, then there exists two facts \tripletHolds{e_1}{r}{e_2} and \tripletHolds{e_1}{r}{e_3} (or respectively with \(\breve{r}\)); however these two facts form a strong negative pair, therefore as per \loss{mtb} their representations must be pulled away from one another.
 
 Despite these assumptions, \textsc{mtb} showcase impressive results, both as a few-shot and supervised pre-training method.
 It obtained state-of-the-art results both on the SemEval 2010 Task 8 dataset with a macro-\(\overHalfdirected{\fone}\) %
 \begin{marginparagraph}[-6mm]
 	As a reminder, \(\overHalfdirected{\fone}\) is the half-directed metric described Section~\ref{sec:relation extraction:supervised evaluation}.
 	It is referred to as ``taking directionality into account'' in the SemEval dataset.
 \end{marginparagraph}
 of 82.7\% and on FewRel with an accuracy of 90.1\% on the 5 way 1 shot task.
 
 \subsection{Self\textsc{ore}}
 \label{sec:relation extraction:selfore}
 Self\textsc{ore} \parencitex{selfore} is a clustering approach similar to the one of \textcite{hasegawa} presented in Section~\ref{sec:relation extraction:hasegawa} but using deep neural network models for extracting sentence representations and for grouping these representations into relation clusters.
 Since they follow the experimental setup of \textcite{fitb}, which we present in Chapter~\ref{chap:fitb}, their results are listed in that chapter.
 
 Self\textsc{ore} uses \textsc{mtb}'s entity markers--entity start \bertcoder{} sentence representation.
 A clustering algorithm could be run to produce relation classes from these representations a la \textcite{hasegawa}.
 However, \textcite{selfore} introduce an iterative scheme to purify the clusters.
 This scheme is illustrated in Figure~\ref{fig:relation extraction:selfore} and works by alternatively optimizing two losses \loss{ac} and \loss{rc}.
 
 The first loss \loss{ac} is the clustering loss which comes from \textsc{dec} \parencitex{dec}.
 \textsc{dec} is a deep clustering algorithm that uses a denoising autoencoder \parencite{dae} to compress the input.
 In their case, the input \(\vctr{h}\) is the sentence encoded by \bertcoder{}.
 The denoising autoencoder is trained layer by layer with a small bottleneck which produces a compressed representation of the sentence \(\vctr{z}=\operatorname{Encoder}(\vctr{h})\).
 This is the space in which the clustering occurs.
 For each cluster \(j=1,\dotsc,K\), a centroid%
 \sidenote{
 	The \(k\)-means clustering algorithm is used to initialize the centroids.
 	In practice, the \(k\)-means clusters could directly be used as soft labels.
 	However, \textcite{selfore} show that this underperforms compared to refining the clusters with \loss{ac}.
 }
 \(\vctr{\mu}_j\) is learned such that a sentence is part of the cluster whose centroid is the closest to its compressed representation.
 This is modeled with a Student's \(t\)-distribution with one degree of freedom centered around the centroid:
 \begin{marginfigure}
 	\centering
 	\input{mainmatter/relation extraction/selfore.tex}
 	\scaption[Self\textsc{ore} iterative algorithm.]{
 		Self\textsc{ore} iterative algorithm.
 		\label{fig:relation extraction:selfore}
 	}
 \end{marginfigure}
 \begin{equation*}
 	q_{ij} = \frac{(1+\|\vctr{z}_i-\vctr{\mu}_j\|^2)^{-1}}{\sum_k (1+\|\vctr{z}_i-\vctr{\mu}_k\|^2)^{-1}}
 \end{equation*}
 To force the initial clusters to be more distinct, a target distribution \(p\) is defined as:
 \begin{equation}
 	p_{ij} = \frac{q_{ij}^2 \divslash f_j}{\sum_k q_{ik}^2 \divslash f_k}
 	\label{eq:relation extraction:selfore target}
 \end{equation}
 where \(f_j=\sum_i q_{ij}\) are soft cluster frequencies.
 To push \(\mtrx{Q}\) towards \(\mtrx{P}\), a Kullback--Leibler divergence is used:
 \begin{equation*}
 	\loss{ac} = \kl(\mtrx{P}\mathrel{\|}\mtrx{Q}) = \sum_{i=1}^{|\dataSet|} \sum_{j=1}^K p_{ij} \log \frac{p_{ij}}{q_{ij}}
 \end{equation*}
 This loss is minimized by backpropagating to the cluster centroids \(\vctr{\mu}_j\) and to the encoder's parameters in the \textsc{dae}.
 Note that the decoder of the \textsc{dae} is only used for initializing the encoder such that the input can be reconstructed.
 
 Optimizing \loss{ac} is the first step of Self\textsc{ore}; it assigns a pseudo-label to each sample in the dataset.
 The second step is to train a classifier to predict these pseudo-labels.
 The classifier is a simple multi-layer perceptron trained with the usual cross-entropy classification loss, which is called \loss{rc} in Self\textsc{ore}.
 This loss also backpropagate to the \bertcoder{} thus changing the sentence representations \(\vctr{h}\).
 Self\textsc{ore} is an iterative algorithm: changing the \(\vctr{h}\) modifies the clustering found by \textsc{dec}.
 Thus, the two steps, clustering and classification, are repeated several times until a stable label assignment is found.
 
 The central assumption of Self\textsc{ore} is that \bertcoder{} already produces a good representation for relation extraction, which, as we saw with the non-fine-tuned \bertcoder{} score on FewRel in Section~\ref{sec:relation extraction:mtb}, is rather accurate.
 However, Self\textsc{ore} also assumes \hypothesis{uniform}, i.e.~that all relations appear with the same frequency.
 This assumption is enforced by \loss{ac}, through the normalization of the target distribution \(\mtrx{P}\) by soft cluster frequencies \(f_j\).%
 \sidenote{For further details, \textcite{dec} contains an analysis of the \textsc{dec} clustering algorithm on imbalanced \textsc{mnist} data.}
 Indeed, the distribution \(\mtrx{P}\) is the original distribution \(\mtrx{Q}\) more concentrated (because of the square) and more uniform (because of the normalization by \(f_j\)).
 
 The interpretation of the concentration effect in terms of modeling hypotheses is more complex.
 The variable \(\vctr{h}\) is the concatenation of the two entity embeddings.
 Let's break down the \bertcoder{} function into two components: \(\operatorname{ctx}_1(s)\) and \(\operatorname{ctx}_2(s)\).
 These are simply the two contextualized embeddings of \texttt{<e1>} and \texttt{<e2>} (Section~\ref{sec:relation extraction:mtb}), in other words the function \(\operatorname{ctx}\) contextualize an entity surface form inside its sentence.
 When two sentence representations \(\vctr{h}\) and \(\vctr{h}'\) are close, their pseudo-labels tend to be the same, and thus their relation also tend to be the same.
 In other words:
 \begin{assumption}[ctxoneadjacency]{\ctxoneadj}
 	Two samples with the same contextualized representation of their entities' surface forms convey the same relation.
 
 	\smallskip
 	\noindent
 	\( \forall (s, \vctr{e}, r), (s', \vctr{e}', r')\in\dataSet_\relationSet\colon \)\\
 	\null\hfill\( \operatorname{ctx}_1(s)=\operatorname{ctx}_1(s') \land \operatorname{ctx}_2(s)=\operatorname{ctx}_2(s') \implies r=r' \)
 \end{assumption}
 If we assume \bertcoder{} only performs entity linking of the entities surface form, then \(\operatorname{ctx}_i(s)=e_i\) for \(i=1,2\), in this case \hypothesis{\ctxoneadj} collapses to \hypothesis{1-adjacency}, the contextualization inside the sentence \(s\) is ignored.
 On the other hand, if we assume \bertcoder{} provides no information about the entities and only encode the sentence, then \(\operatorname{ctx}_i(s)=s\) for \(i=1,2\) and \hypothesis{\ctxoneadj} only states that the entity identifiers \(\vctr{e}\in\entitySet^2\) should have no influence on the relation.
 The effective repercusion of \hypothesis{\ctxoneadj} lies somewhere half-way between these two extremes.